指针分析的性质

Flow sensitive

Flow-sensitive	Flow-insensitive
Respect the execution order of the program	Ignore the control-flow order, treat the program as a set of unordered statements
Maintain a map of points-to relations at each program location	Maintain one map of points-to relations for the whole program

Context sensitive

Context-sensitive	Context-insensitive
Distinguish different calling contexts of a method	Merge all calling contexts of a method
Analyze each method multiple times, once for each context	Analyze each method once

Analysis Scope

Whole-program	Demand-driven
Compute points-to information for all pointers in the program	Only compute points-to information for the pointers that may affect specific sites of interest (on demand)
Provide information for all possible clients	Provide information for specific clients

指针分析的关注语句

只有四条语句对指针分析而言有意义： - Assign - Address - Load - Store

在Java中，分别对应：

a = b;       // 1
C c = new C; // 2
d = c.f;     // 3
c.f = a;     // 4

指针分析的图

启示：同一个程序的指针关系可以用不同的图表示

PFG (Pointer Flow Graph)

PFG是一张有向图，图上的节点是指针（对Java而言是引用，包括引用变量和对象的引用成员）。$x\rightarrow y$代表$x$指向的对象有可能流向$y$。

New语句给出了一个指针初始可能指向的抽象对象。指针分析就是PFG上的传递闭包。

PFG的循环依赖看似指针分析的过程是先求出PFG，再在PFG上求一个传递闭包。但是PFG的构建实际上也依赖指针分析的结果。我们同样要将PFG的构建视为一个不等式约束问题，利用格理论求解。动态地向PFG上添加边，直到没有边被添加。
算法实现细节 TODO：differential propagate

Constraint Graph

SVF transforms LLVM instructions into a graph representation, PAG. Each node (PAGNode) represents a pointer, and each edge (PAGEdge) represents a constraint between two pointers.

There are two main kinds of SVFVar: ValVar (ValPN) represents a pointer and ObjVar (ObjPN) represents an abstract object. GepObjVar (GepObjPN), which is a subclass of ObjVar (ObjPN), represents a field of an aggregate object. GepValVar (GepValPN), which is a subclass of ValVar (ValPN), represents an introduced dummy node to achieve field sensitivity when handling external library calls (e.g., memcpy, where pointers (LLVM Values) that point to the fields of an struct do not explicitly appear at an instruction). RetPN represents the unique return of a procedure. VarArgPN denotes a variadic argument of a procedure.

跨procedure指针分析

添加call语句的规则。

只需要分析reachable的method。以main作为root method开始。分析一个method时，addReachable（处理new 和赋值语句）并更新work list。如果不是root method还要应用call的规则。然后继续大循环处理load和store。